package demo.practice.competition;

import demo.practice.tree.segment.SegmentTree;

import java.util.*;

public class P5806 {

    public static void main(String[] args) {
        P5806 p5806 = new P5806();
        //[[1,4,5],[1,4,7],[4,7,1],[4,7,11]]  [[1,4,12],[4,7,12]]   [[1, 7, 12]]
        List<List<Long>> lists = p5806.splitPainting(new int[][]{{1, 4, 5}, {1, 4, 7}, {4, 7, 1}, {4, 7, 11}});
        System.out.println(lists);
        //[[1,4,14],[4,7,16]]
        //[[4,6,16],[1,3,14]]
    }

    public List<List<Long>> splitPainting(int[][] segments) {
        int max = 0;
        for (int[] segment : segments) {

            max = Math.max(segment[1], max);
        }

        SegmentTree tree = new SegmentTree(new long[max + 1]);

        for (int[] segment : segments) {
            for (int i = segment[0]; i < segment[1]; i++) {
                tree.update(i, (long) tree.data[i] + (long) segment[2]);
            }
        }

//        Map<Integer, List<Long>> map= new HashMap<>();
        //Map<Long, int[]> map = new HashMap<>();
        int bg = -1;
        int end = -1;
        List<List<Long>> res = new ArrayList<>();
        for (int i = 1; i < tree.data.length; i++) {
            long a = tree.data[i];
            if (a != 0) {
                if (bg == -1) {
                    bg = i;
                }
                end = i;
                if (i == tree.data.length - 1 || !tree.jys[i].toString().equals(tree.jys[i + 1].toString())) {
                    res.add(new ArrayList<>(Arrays.asList((long) bg, (long) end + 1, a)));
                    bg=-1;
                }
            }
        }
        //List<List<Long>> res = new ArrayList<>();

       /* for (Map.Entry<Long, int[]> en : map.entrySet()) {
            int[] arr = en.getValue();
            res.add(new ArrayList<>(Arrays.asList((long) arr[0], (long) arr[1] + 1, en.getKey())));
        }*/
        return res;
    }

    public class SegmentTree {
        public long[] tree;
        public long[] data;
        public StringBuffer[] jys;


        SegmentTree(long[] data) {

            if (data == null || data.length == 0) {
                throw new RuntimeException("初始化数组不为空(can't build a no element tree)");
            }

            this.data = data;
            jys = new StringBuffer[data.length];
            //Arrays.fill(jys, new StringBuffer());   //坑爹，同一个对象
            for (int i=0;i<jys.length;i++) {
                jys[i] = new StringBuffer();
            }

            tree = new long[data.length * 4];
            build(0, 0, data.length - 1);
        }

        //        【1、2、3、4、5、6、7】   treeindex=0
        //           /           \
        //    【1、2、3]        【4、5、6、7】          treeindex=1和 treeindex=2
        //     /    \            /    \
        // 【1】 【2、3】      【4、5】  【6、7】       treeindex分别等于  3、4、5、6
        //       /  \        /   \    /  \          //根据完全二叉树的性质 父子关系为 父为n，则有左子为 2*n+1 右子为2*n+2
        //     【2】【3】    【4】【5】【6】【7】


        /**
         * @param treeindex tree对应节点的索引
         * @param l         构建时，arr的左边界
         * @param r         构建时，arr的右边界
         */
        private void build(int treeindex, int l, int r) {
            if (l == r) {
                tree[treeindex] = data[l];
                return;
            }

            int mid = l + (r - l) / 2;
            //左边
            build(treeindex * 2 + 1, l, mid);
            //右边
            build(treeindex * 2 + 2, mid + 1, r);
            //左边加上右边得到父亲节点
            tree[treeindex] = tree[treeindex * 2 + 1] + tree[treeindex * 2 + 2];
        }

        /**
         * 查询接口
         */
        public long query(int l, int r) {
            //查询数组区间 l~r的和
            if (l > r) {
                throw new RuntimeException("输入的区间错误(input l must litte than r)");
            }
            return query(0, 0, data.length - 1, l, r);
        }

        /**
         * 查询辅助函数，归并思想
         *
         * @param treeindex tree对应节点的索引
         * @param tl        tree当前值对应  arr范围的左边界
         * @param tr        tree当前值对应  arr范围的右边界
         *                  综合起来相当于 tree[treeindex] = arr[tl~tr]的和
         * @param l         查询范围的左边界
         * @param r         查询范围的右边界
         */
        private long query(int treeindex, int tl, int tr, int l, int r) {
            //刚好就查到了
            if (tl == l && tr == r) {
                return tree[treeindex];
            }

            //直接越界了，查不到
            if (l > tr || r < tl) {
                return 0;
            }

            int mid = tl + (tr - tl) / 2;
            //l~ mid为左边区间、 (mid + 1)~r 为右边区间
            if (r <= mid) {
                //直接去左边区间找
                return query(treeindex * 2 + 1, tl, mid, l, r);
            }
            if (l > mid) {
                //直接去右边区间找
                return query(treeindex * 2 + 2, mid + 1, tr, l, r);
            }
            return query(treeindex * 2 + 1, tl, mid, l, mid) +
                    query(treeindex * 2 + 2, mid + 1, tr, mid + 1, r);
        }

        /**
         * 更新接口
         */
        public void update(int index, long value) {
            jys[index].append(value);
            if (index > data.length - 1 || index < 0) {
                throw new RuntimeException("输入的区间错误(input l must litte than r)");
            }
            data[index] = value;
            update(0, 0, data.length - 1, index, value);
        }

        /**
         * 更新辅助函数，归并思想
         *
         * @param treeindex tree对应节点的索引
         * @param tl        tree当前值对应  arr范围的左边界
         * @param tr        tree当前值对应  arr范围的右边界
         *                  综合起来相当于 tree[treeindex] = arr[tl~tr]的和
         */
        private void update(int treeindex, int tl, int tr, int index, long value) {

            if (tl == tr && index == tl) {
                tree[treeindex] = value;
                return;
            }

            int mid = tl + (tr - tl) / 2;
            //l~ mid为左边区间、 (mid + 1)~r 为右边区间
            if (index <= mid) {
                update(treeindex * 2 + 1, tl, mid, index, value);
            }
            if (index > mid) {
                update(treeindex * 2 + 2, mid + 1, tr, index, value);
            }
            //需要在此更新一下父节点
            tree[treeindex] = tree[treeindex * 2 + 1] + tree[treeindex * 2 + 2];
        }
    }
}
